<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 二叉树 */
        let treeArr = [2, 1, 3]
        console.log('treeArr', treeArr)
        // let treeArr = [5, 1, 4, null, null, 3, 6]
        // let treeArr = [1, null, 2, 3]
        function TreeNode(val, left, right) {
            this.val = (val === undefined ? 0 : val)
            this.left = (left === undefined ? null : left)
            this.right = (right === undefined ? null : right)
        }
        //顺序存储数组转换成层序遍历嵌套数组
        function levelOrder(arr) {
            let res = []
            let index = 2
            res.push([arr.shift()])
            while (arr.length) {
                res.push([])
                for (let i = 0; i < index; i++) {
                    res[res.length - 1].push(arr.shift())
                }
                index += index
                if (index > arr.length) index = arr.length
            }
            return res
        }
        //利用 后序遍历 左-右-根 从树顶到树根 逐层生成
        function traversToTree(arr) {
            let root
            let leafarr = arr.pop()
            //初始叶子节点数组
            let leafNodeArr = leafarr.map(item => item ? new TreeNode(item, null, null) : null)
            while (arr.length) {
                let levelArr = arr.pop()
                let newleafNodeArr = []
                //根据每层数据渲染对应层的TreeNode
                while (levelArr.length) {
                    let item = levelArr.shift()
                    root = item ? new TreeNode(item, leafNodeArr.shift(), leafNodeArr.shift()) : null
                    newleafNodeArr.push(root)
                    //如果不是最底层叶子 那么要讲站位的null出队列
                    if (!root && leafNodeArr.notleaf) {
                        leafNodeArr.shift()
                        leafNodeArr.shift()
                    }
                }
                //将新一层的子节点作为叶子节点
                leafNodeArr = newleafNodeArr
                leafNodeArr.notleaf = true //标识不是最底层叶子节点
            }
            console.log("file: leetcode.html ~ line 57 ~ root", root)
            return root
        }
        //获取二叉树
        let binaryTree = traversToTree(levelOrder(treeArr))


        /* 
            利用中序遍历验证是否是二叉搜索树  按照中序遍历的结果 应该是足个递增
         */
        //中序遍历
        function inorderTraversal(root) {
            let res = []
            let stk = []
            while (root || stk.length) {
                while (root) {
                    stk.push(root)
                    root = root.left
                }
                root = stk.pop()
                res.push(root.val)
                //当某个结点有右子树的时候 去中序遍历这个右子树 此时此节点的左子结点和本身都已经做个处理
                root = root.right

            }
            return res
        }
        //验证是否是二叉搜索树 结构与中序遍历一致；按照中序操作 每次操作的数据应该都比上一个大
        function isValidBST(root) {
            let stk = []
            let oldVal = -Infinity
            while (root || stk.length) {
                while (root) {
                    stk.push(root)
                    root = root.left
                }
                root = stk.pop()
                if (oldVal >= root.val) return false
                //当某个结点有右子树的时候 去中序遍历这个右子树 此时此节点的左子结点和本身都已经做个处理
                root = root.right

            }
            return true
        }
        console.log(isValidBST(binaryTree))

        /* 
            根据前序遍历和中序遍历结果生成二叉树
        */
        let preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
        var buildTree = function (preorder, inorder) {
            if (!preorder.length || !inorder.length) return null
            const rootVal = preorder[0]
            const node = new TreeNode(rootVal)
            const i = inorder.indexOf(rootVal)
            node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i))
            node.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1))
            return node

        };
        console.log(buildTree(preorder, inorder))
    </script>
</body>

</html>